package com.ai.bmg.bmgwebboot.test.zk;


import java.util.*;

/**
 * 功能描述
 *
 * @author cWX1142527
 * @since 2023年01月18日
 */
public class Java_57_插入区间 {
    public static void main(String args[]) {
        int[] newInterval = new int[]{10,12};
        int[][] intervals = new int[][]{{1,2},{3,4},{7,8},{9,11}};
        // 方法1
        int[][] retInts = insertIntervalArray(intervals,newInterval);

        // 方法2
        int[][] retInts1 = insertIntervalArray1(intervals,newInterval);
        System.out.println(retInts);
    }

    public static int[][] insertIntervalArray1(int[][] intervals, int[] newInterval) {
       // (x,y)     x > arr[r] || y < arr[l] 时没有交集
        // 交集  max(x,arr[l]) min(y,arr[r])
        // 并集 min(x,arr[l])max (y,arr[r])
        List<int[]> retList = new ArrayList<>();
        int[] tempArray = newInterval;
        boolean isAddTemp = false;
        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][1] < newInterval[0]) {
                retList.add(intervals[i]);
            } else if (tempArray[1] < intervals[i][0]) {
                if (!isAddTemp) {
                    retList.add(tempArray);
                    isAddTemp = true;
                }
                retList.add(intervals[i]);
            } else {
                // 取并集
                tempArray = new int[]{Math.min(tempArray[0], intervals[i][0]), Math.max(tempArray[1], intervals[i][1])};
            }
        }
        if (!isAddTemp) {
            retList.add(tempArray);
        }
        return retList.toArray(new int[retList.size()][]);
    }

    public static int[][] insertIntervalArray(int[][] intervals, int[] newInterval) {
        // 将 intervals 修改成 int[] 数组
        int[] temVals = new int[intervals.length * 2];
        for (int i = 0; i < intervals.length; i++) {
            temVals[i * 2] = intervals[i][0];
            temVals[i * 2 + 1] = intervals[i][1];
        }
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        int len = temVals.length;
        int low = 0;
        int hight = len - 1;
        int mid = 0;
        int[][] retInt = new int[len + 1][];
        if (newStart > temVals[len - 1]) {
            for (int i = 0; i < len; i++) {
                retInt[i] = intervals[i];
            }
            retInt[len] = newInterval;
            return retInt;
        }

        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }

        // 找到 起止点所在的 区间的 下标位置 ，然后再找到 结束点所在的下标位置
        int[] startIndxAndVal = findIndex(low, hight, temVals, newStart, intervals, false);
        int[] endIndxAndVal = findIndex(low, hight, temVals, newEnd, intervals, true);
        // 这里进行判断处理合并
        List<int[]> retInt1 = new ArrayList<>();
        for(int i = 0; i < intervals.length; i++) {
            if (i < startIndxAndVal[0]) {
                retInt1.add(intervals[i]);
                continue;
            }
            if (i == startIndxAndVal[0] && i == endIndxAndVal[0]) {
                if (i == intervals.length - 1) {
                    int[] retInfo = new int[2];
                    retInfo[0] = startIndxAndVal[1] < intervals[i][0] ? startIndxAndVal[1] : intervals[i][0];
                    retInfo[1] = endIndxAndVal[1] < intervals[i][1] ? intervals[i][1] : endIndxAndVal[1];
                    retInt1.add(retInfo);
                    continue;
                }
                // 【3,4】 插入在【1，2】【5，6】
                if (startIndxAndVal[1] != intervals[i][0]) {
                    retInt1.add(startIndxAndVal);
                    retInt1.add(intervals[i]);
                } else {
                    retInt1.add(intervals[i]);
                }
            } else if (i == startIndxAndVal[0]) {
                retInt1.add(new int[2]);
                retInt1.get(retInt1.size() - 1);
                retInt1.get(retInt1.size() - 1)[0] = intervals[i][0] <= startIndxAndVal[1] ? intervals[i][0] : startIndxAndVal[1];
            } else if (i == endIndxAndVal[0]){
                retInt1.get(retInt1.size() - 1)[1] = intervals[i][1] <= endIndxAndVal[1] ? endIndxAndVal[1] : intervals[i][1];
            } else if (i < endIndxAndVal[0]){
                continue;
            } else {
                retInt1.add(intervals[i]);
            }

        }
        int[][] result = new int[retInt1.size()][];
        for (int i = 0; i < retInt1.size(); i++) {
            result[i] = retInt1.get(i);
        }
        return result;
    }

    public static int[] findIndex(int low, int hight, int[] temVals, int val, int[][] intervals,
                                  boolean isEnd) {
        int mid = 0;
        while (low < hight) {
            mid = (low + hight) / 2;
            if (val == temVals[mid]) {
                break;
            } else if (val < temVals[mid]) {
                hight = mid;
            } else {
                low = mid + 1;
            }
        }

        int[] indxAndVal = new int[2];
        indxAndVal[0] = mid / 2;
        if (temVals[mid] == val) {
            indxAndVal[1] = isEnd ? intervals[mid / 2][1] : intervals[mid / 2][0];
        } else {
            // 偶数位置时
            if (mid % 2 == 0) {
                indxAndVal[1] =  val;
            } else {
                indxAndVal[1] = isEnd ? intervals[mid / 2][1] : intervals[mid / 2][0];
            }
        }
        return indxAndVal;
    }
}